#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e7;
bool a[maxn+40];
int prime[maxn+10];

int main()
{
	int cnt = 0;
	for(int i = 2;i < maxn;i++)
	{
		if(!a[i]) 
			prime[cnt++]=i;

		for(int j = 0;j < cnt;j++)
		{
			if(i*prime[j] > maxn)
				break;
			a[i*prime[j]] = true;
			if(i%prime[j] == 0)
				break;
		}
	}
	a[1] = !a[1];
	long long t, n, m; 
	cin>>t;
	while(t--)
	{
		long long sum = 0;
		cin>>n>>m;
		if(n > m)
			swap(n,m);
		int k = sqrt(m)+1;
		for(int i = sqrt(n);i <= k;i++)
		{
			int tt = i*i;
			if(!a[i] && n<= tt && tt <= m)
				sum += tt;
		}
		cout<<sum<<endl;
	}
	
    return 0;
}

